package 左哥算法.ch08前缀树;

import java.util.HashMap;
import java.util.Map;

public class TrieNode {
    int pass;   //有多少个单词通过该节点
    int end;    //有多少个单词以该节点结尾
    Map<Character,TrieNode> nexts;       //该节点通往的节点

    public TrieNode(int pass, int end) {
        this();
        this.pass = pass;
        this.end = end;
    }

    public TrieNode() {
        this.nexts = new HashMap<>();
    }

    /**
     * 插入操作：
     *      依次对字符串进行遍历，每走到一个节点，对该点pass++，
     *      如果不能走通则对下一个节点进行新建，并将其放入当前节点的nexts中
     */
    public void insert(String word){
        char[] chars = word.toCharArray();
        TrieNode curr=this;
        for (char c : chars) {
            curr.pass++;
            TrieNode trieNode = curr.nexts.get(c);
            if (trieNode==null) {
                trieNode=new TrieNode();
                curr.nexts.put(c,trieNode);
            }
            curr=trieNode;
        }
        curr.pass++;
        curr.end++;
    }

    /**
     * 查找该单词出现的次数
     */
    public int search(String word){
        char[] chars = word.toCharArray();
        TrieNode curr=this;
        for (char c : chars) {
            curr = curr.nexts.get(c);
            if (curr==null){
                return 0;
            }
        }
        return curr.end;
    }

    /**
     * 获取该前缀出现过多少次
     */
    public int startsWith(String prefix) {
        char[] chars = prefix.toCharArray();
        TrieNode curr=this;
        for (char c : chars) {
            curr = curr.nexts.get(c);
            if (curr==null){
                return 0;
            }
        }
        return curr.pass;
    }

    /**
     * 删除单词（将该单词的次数，以及以该单词为前缀的次数，都减一）
     */
    public void delete(String word){
        if (search(word)==0){
            return;
        }
        char[] chars = word.toCharArray();
        TrieNode curr=this;
        for (char c : chars) {
            curr.pass--;
            curr=curr.nexts.get(c);
        }
        curr.pass--;
        curr.end--;
    }
}
